// https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/
// Created by ade on 2022/9/7.
//我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
//
//例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
//
//本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。
//
//注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
//
// 输入: s = "ABC"
//输出: 10
//解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
//     其中，每一个子串都由独特字符构成。
//     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
// 输入: s = "ABA"
//输出: 8
//解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

// 原问题为求所有子数组的唯一字符数量和，其可等价为求每个 s[i] 对答案的贡献，即每个 s[i] 可作为多少个子数组的唯一元素。
//
//假定我们能预处理出两数组 l 和 r 分别代表 s[i] 作为子数组唯一字符时，其所能到达的最远两端：
//
//l[i] = a 代表下标 a 为 s[i] 能够作为子数组唯一字符时的最远左边界，即为 s[i] 左边第一个与 s[i] 值相同的位置（若不存在，则为 a = -1）
//r[i] = b 代表跳表 b 为 s[i] 能够作为子数组唯一字符时的最远右边界，即为 s[i] 右边第一个与 s[i] 值相同的位置（若不存在，则为 b = n）
//子数组左端点个数为 (i - a) 个，右端点个数为 (b - i) 个，根据乘法原理可知，子数组个数为两者乘积。
//
//预处理 l 和 r 只需要使用遍历计数即可。
//


#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


using namespace std;

class Solution {
public:
    int uniqueLetterString(string s) {
        int len = s.size();
        vector<int> left(len, -1);
        vector<int> right(len, len);
        unordered_map<int, int> m = {}; // 上一个 字符-位置
        for (int i = 0; i < len; i++) {
            int c = s[i] - 'a';
            if (m.find(c) != m.end()) {
                right[m[c]] = i;
                left[i] = m[c];
            }
            m[c] = i;
        }
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += (i - left[i]) * (right[i] - i);
        }
        return sum;
    }
};

int main() {
    Solution so;
    cout << so.uniqueLetterString("leetcode") << endl;
    return 0;
}